package com.test.daily.leetcode.y2022.m05.day0515.v02;

import java.util.HashMap;

/**
 * @author Tom on 2022/5/15
 */
public class Solution {
    public static void main(String[] args) {
        int[] arr = new int[]{1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7};
        System.out.println(findK(arr, 2, 3));
    }

    //  数组中有个数出现K次,其他数出现M次,找到出现K次的数字
    public static int findK(int[] arr, int K, int M) {
        HashMap<Integer, Integer> map = createMap();
        int ERROR = -1;
        int[] bitCounts = new int[32];
        for (int i = 0; i < arr.length; i++) {
            int tmp = arr[i];
            while (tmp != 0) {
                int rightestOne = tmp & (~tmp + 1);
                bitCounts[map.get(rightestOne)]++;
                tmp ^= rightestOne;
            }
        }
        int ans = 0;
        for (int i = 0; i < bitCounts.length; i++) {
            if (bitCounts[i] % M == K) {
                ans |= 1 << i;
            } else if (bitCounts[i] % M != 0) {
                return ERROR;
            }
        }
        if (ans == 0) {
            int k = 0;
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == 0) k++;
            }
            if (k % M != K) {
                return ERROR;
            }
        }
        return ans;
    }

    public static HashMap<Integer, Integer> createMap() {
        HashMap<Integer, Integer> map = new HashMap<>();
        int k = 1;
        for (int i = 0; i < 32; i++) {
            map.put(k, i);
            k <<= 1;
        }
        return map;
    }
}
